Stream ciphers are widely used in cryptographic applications to encrypt and transmit messages of arbitrary length. The major issue with a block cipher is that messages can only be of a fixed length. This issue is resolved by using Stream Ciphers.
The functioning of stream ciphers depend heavily on the ability to design something that can produce cryptographically secure "random" numbers, in a manner replicable by the receiver of the message, but completely unpredictable to a determined attacker intercepting your data.
Before we begin Stream Ciphers, we gotta take a look at what symmetric ciphers are, and why we need stream ciphers.
Symmetric Ciphers are ciphers that are pretty much exactly what they sound like: they use a symmetric approach to encrypt and decrypt. In other words, the same key is used for both encryption and decryption of the message.
A symmetric cipher is denoted by the following things:
It's defined over three spaces
It involves two algorithms:
Both these algorithms are to be "efficient" (not hard problems (run in polynomial time)).
$$ \mathcal{E} : \mathcal{K} \times \mathcal{M} \rightarrow \mathcal{C} \\ \mathcal{D} : \mathcal{K} \times \mathcal{C} \rightarrow \mathcal{M} \\ $$$$ \text{Also, } \mathcal{D}(k, \mathcal{E}(k, m)) = m $$In other words, the encryption of a message under a key gives a ciphertext. The decryption of that ciphertext under the same key must return the same message.
The One Time Pad is a basic symmetric cipher that works by simply XORing a key to a message of the same length. The key is used for exactly one message block and is never re-used.
$\mathcal{M}, \mathcal{C}, \mathcal{K} : \{0, 1\}^n$
Here $n$ is the number of bits you want for your message space.
Note that the key $k$ for the One Time Pad can be used only ONCE. This is the whole reason we call it the One Time Pad.
This method actually has perfect security. The major disadvantage is that the secret key must be created anew for each message and known to both parties, and also the key length is the same as the message length, so at that point you might as well transmit the message directly instead of finding some secret method to share the key.
Below is an implementation of the One Time Pad.
In [20]:
import random, string
def randomstr(length):
return ''.join(random.choice(string.ascii_letters) for i in xrange(length))
def str_xor(s1, s2) :
# pairwise alphabets from the strings are returned by zip
# these are converted to numbers, then xor-ed, then made to a list, then joined as chars
return ''.join([chr(ord(c1)^ord(c2)) for (c1, c2) in zip(s1, s2)])
message = raw_input('Enter message string: ')
key = randomstr(len(message))
print "Key: " , key
ciphertext = str_xor(key, message)
print "Ciphertext (hexform): ", repr(ciphertext)
print "Original message: ", str_xor(key, ciphertext)
The basic idea is this: The ciphertext must reveal NO information about the plaintext or the key.
A cipher $(\mathcal{E}, \mathcal{D})$ has perfect secrecy if:
$$ \text{Pr}[\mathcal{E}(k, m_0) = c] = \text{Pr}[\mathcal{E}(k, m_1) = c] \quad \forall (m_0, m_1) \in \mathcal{M} $$where $m_0$ and $m_1$ lie in the message space,
$k \in \mathcal{K}$ and is uniformly distributed over it,
$c \in \mathcal{C}$
The whole point, as given in the first line, is that the ciphertext must tell nothing about the plaintext. Thus, as the key is what hinges together the whole cryptosystem, it is imperative for the key to not be biased in distribution. Moreover, if the attacker gets his hands on a ciphertext, they must not be able to tell if the message is some $m_1$, or some $m2$, or anything else really. In other words, for all pairs $m_0$ and $m_1$ in the message space, the attacker will not be able to distinguish from the ciphertext if the original message is one or the other, simply because the probability of any of those messages being the original is exactly the same.
Simply put, you just can't tell what the message is from the ciphertext. This is in line with the basic aim for perfect secrecy.
A OTP has perfect secrecy. Intuitively, we can understand this easily enough. Consider that the XOR operation is basically a bit-flip or a no-bit-flip. If the second input to the XOR is 0, it retains the first input. If the input is 1, it flips the first input.
In other words:
$$ x \oplus 0 = x \\ x \oplus 1 = x\text{-flipped} $$Thus, a randomly generated one-time key (uniformly distributed over the keyspace) will either flip or not flip each bit in the message string with an equal probability. In other words, given say a bit 1 in the ciphertext, we have no idea if the message originally contained a flipped bit (0) or a non-flipped bit (1). This makes the message perfectly unintelligible to the attacker who has no knowledge of the key.
Turns out, Shannon proved that if you need perfect secrecy, the number of keys in the keyspace must be greater than or equal to the number of possible messages. In other words, $\left | \mathcal{K} \right | \geq \left | \mathcal{M} \right |$.
If we want all possible messages of length $n$ bits, then naturally according to the above, the length of the keys themselves must be equal to or more than the length of the messages.
That sucks. That really sucks. It essentially means that communicating your key securely to a third party will in essence be at least just as hard as communicating the message itself directly, making the OTP not very useful for actual communication.
Why do we need a stream cipher? As explained right above, a One Time Pad is totally useless for actual communication, as the length of the key must be equal to the message length (at the least), so we'd rather transmit the message directly instead of transmitting keys.
Here, instead of using a random key as done in the One Time Pad, we'll be using a pseudorandom key that's generated using a random "master" key.
A PseudoRandom Number Generator (PRNG) is a function that takes a "seed" input and generates a "random" output. The idea is this: the size of the output must be significantly greater than the size of the input. Also, being a function (in the mathematical sense), for the same seed input, the function must give the same output.
Mathematically, the PRNG is a function $\mathcal{G}$ defined on:
$$ \mathcal{G} : \{0, 1\}^s \rightarrow \{0, 1\}^n \qquad n \gg s $$where $n$ is the size of the "random" output and $s$ is the size of the seed.
Some requirements are present:
Mathematically, the definition of what makes a cryptographically secure PRNG, or a CSPRNG, is the factor of unpredictability. The output of the PRNG must not be predictable.
Unpredictability of a PRNG simply means that, given some initial bits churned out by the PRNG with some key (seed), there must be no way to predict the following bits efficiently.
In other words, for a predictable PRNG, there exists some $i$ such that given $\mathcal{G}(k) \mid _{1, 2, .., i}$, we can use an efficient (polynomial-time) algorithm to get bits $\mathcal{G}(k) \mid _{i+1, i+2, .., n}$.
The attack for this works in a pretty simple manner. The attacker has access to the ciphertext traveling on the unsecured network. If he knows a small initial portion of the message (for example, HTTP headers which always follow the same format) and XORs it with the ciphertext, he can get the initial few bits of the PRNG. If these bits are enough to predict the next $r$ bits of the PRNG, then he can simply XOR those predicted bits with the ciphertext to recover more bits of the message.
Mathematically then, an predictable PRNG can be defined as follows:
An predictable PRNG is a PRNG where there exists a polynomial-time algorithm $\mathcal{A}$ and a number of bits $i$ such that
$$ \text{Pr}[\mathcal{A}(\mathcal{G}(k)\mid _{1..i})\ = \mathcal{G}(k)\mid _{i+1}] \geq \frac{1}{2} + \epsilon $$where $k$ is the key (seed), for some $\epsilon$ that's non-negligible.
Thus, simply by inverting the above, an unpredictable PRNG must have the property that for all $i$, the value output cannot be predicted by an efficient algorithm.